package cn.edu.jxau.test;

/**
 * 求有环单链表的环连接点位置
 * 
 * @author Fudashi
 */
public class Main {

	public static void main(String[] args) {

		Node node1 = new Node(1);
		Node node2 = new Node(2);
		Node node3 = new Node(3);
		Node node4 = new Node(4);
		Node node5 = new Node(5);
		Node node6 = new Node(6);
		Node node7 = new Node(7);
		Node node8 = new Node(8);
		Node node9 = new Node(8);
		Node node10 = new Node(10);
		Node node11 = new Node(11);
		Node node12 = new Node(12);
		Node node13 = new Node(13);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		node5.next = node6;
		node6.next = node7;
		node7.next = node8;
		node8.next = node9;
		node9.next = node10;
		node10.next = node11;
		node11.next = node12;
		node12.next = node13;
		System.out.println(ciycleNode(node1).data);
	}

	/**
	 * 如果有环的话返回第一个环节点，如果没有则返回null
	 * 
	 * @param first
	 * @return
	 */
	public static Node ciycleNode(Node first) {

		Node slow = first;
		Node fast = first;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			if (slow == fast) {
				break;
			}
		}
		if (fast == null || fast.next == null) { // 不成环
			return null;
		}
		Node c1 = first;
		Node c2 = fast;
		while (c1 != c2) {
			c1 = c1.next;
			c2 = c2.next;
		}
		return c1;
	}
}

class Node {

	public int data;
	public Node next;

	public Node(int data) {
		this.data = data;
	}
}